package leetcode.tree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author wangmaolin1
 * @date 2023/11/11 12:42
 */
public class _652 {
    private Map<String, Integer> subTree = new HashMap<>();
    private List<TreeNode> res = new ArrayList<>();

    /**
     * 给你一棵二叉树的根节点 root ，返回所有 重复的子树 。
     * <p>
     * 对于同一类的重复子树，你只需要返回其中任意 一棵 的根结点即可。
     * <p>
     * 如果两棵树具有 相同的结构 和 相同的结点值 ，则认为二者是 重复 的。
     */
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        track(root);
        return res;
    }

    public String track(TreeNode root) {
        if (root == null) {
            return "#";
        }
        String left = track(root.left);
        String right = track(root.right);
        String cur = left + "," + right + "," + root.val;
        int subNum = subTree.getOrDefault(cur, 0);
        if (subNum == 1) {
            res.add(root);
        }
        subTree.put(cur, subNum + 1);
        return cur;
    }
}
